\section{Subquadratic time offline token-forwarding algorithms}
\label{sec:centralized}
In this section, we give two centralized algorithms for the $k$-gossip
problem in the offline model. We present an $O(\min\{n\sqrt{k\log
  n}, nk\})$ round algorithm in Section \ref{sec:upper}. Then we
present a bicriteria $\rb{O(n^\epsilon), \log n}$-approximation
algorithm in Section \ref{sec:approx}, which means if $L$ is the
number of rounds needed by an optimal algorithm where one token is
broadcast by every node per round, then our approximation algorithm
will complete in $O(n^\epsilon L)$ rounds and the number of tokens
broadcast by any node is $O(\log n)$ in any given round. Both of these
algorithms uses a directed capacitated leveled graph constructed from
the sequence of communication graphs which we call the {\em evolution
  graph}.

\smallskip
\noindent
{\em Evolution graph}: Let $V$ be the set of nodes. Consider a dynamic
network of $l$ rounds numbered $1$ through $l$ and let $G_i$ be the
communication graph for round $i$. The evolution graph for this
network is a directed capacitated graph $G$ with $2l+1$ levels
constructed as follows. We create $2l+1$ copies of $V$ and call them
$V_0, V_2, \dots, V_{2l}$. $V_i$ is the set of nodes at level $i$ and
for each node $v$ in $V$, we call its copy in $V_i$ as $v_i$. For $i =
1, \ldots, l$, level $2i-1$ corresponds to the beginning of round $i$
and level $2i$ corresponds to the end of round $i$. Level $0$
corresponds to the network at the start. Note that the end of a
particular round and the start of the next round are represented by
different levels. There are three kinds of edges in the graph. First,
for every round $i$ and every edge $(u,v) \in G_i$, we place two
directed edges with unit capacity each, one from $u_{2i-1}$ to
$v_{2i}$ and another from $v_{2i-1}$ to $u_{2i}$. We call these edges
{\em broadcast edges} as they will correspond to broadcasting of
tokens; the unit capacity on each such edge will ensure that only one
token can be sent from a node to a neighbor in one round. Second, for
every node $v$ in $V$ and every round $i$, we place an edge with
infinite capacity from $v_{2(i-1)}$ to $v_{2i}$. We call these edges
{\em buffer edges} as they ensure tokens can be stored at a node from
the end of one round to the end of the next. Finally, for every node
$v \in V$ and every round $i$, we also place an edge with unit
capacity from $v_{2(i-1)}$ to $v_{2i-1}$. We call these edges as {\em
  selection edges} as they correspond to every node selecting a token
out of those it has to broadcast in round $i$; the unit capacity
ensures that in a given round a node must send the same token to all
its neighbors. Figure \ref{fig:evolution} illustrates our
construction, and Lemma~\ref{lem:level.steiner} explains its
usefulness.

\begin{figure}[ht]
\begin{center}
\includegraphics[width=5in]{level.jpg}
\caption{An example of how to construct the evolution graph from a
  sequence of communication graphs.}
\label{fig:evolution}
\end{center}
\end{figure}

\begin{lemma}
\label{lem:level.steiner}
Let there be $k$ tokens, each with a source node where it is present
in the beginning and a set of destination nodes to whom we want to
send it. It is feasible to send all the tokens to all of their
destination nodes in a dynamic network using $l$ rounds, where in each
round a node can broadcast only one token to all its neighbors, if and
only if $k$ directed Steiner trees can be packed in the corresponding
evolution graph with $2l + 1$ levels respecting the edge capacities,
one for each token with its root being the copy of the source node at
level $0$ and its terminals being the copies of the destination nodes
at level $2l$.
\end{lemma}
\begin{proof}
Assume that $k$ tokens can be sent to all of their destinations in $l$
rounds and fix one broadcast schedule that achieves this. We will
construct $k$ directed Steiner trees as required by the lemma based on
how the tokens reach their destinations and then argue that they all
can be packed in the evolution graph respecting the edge
capacities. For a token $i$, we construct a Steiner tree $T^i$ as
follows.  For each level $j \in \{0, \ldots, 2l\}$, we define a set
$S^i_j$ of nodes at level $j$ inductively starting from level $2l$
backwards.  $S^i_{2l}$ is simply the copies of the destination nodes
for token $i$ at level $2l$. Once $S^i_{2(j+1)}$ is defined, we define
$S^i_{2j}$ (respectively $S^i_{2j+1}$) as: for each $v_{2(j+1)} \in
S^i_{2(j+1)}$, include $v_{2j}$ (respectively nothing) if token $i$
has reached node $v$ after round $j$, or include a node $u_{2j}$
(respectively $u_{2j+1}$) such that $u$ has token $i$ at the end of
round $j$ which it broadcasts in round $j+1$ and $(u,v)$ is an edge of
$G_{j+1}$. Such a node $u$ can always be found because whenever
$v_{2j}$ is included in $S^i_{2j}$, node $v$ has token $i$ by the end
of round $j$ which can be proved by backward induction staring from $j
= l$. It is easy to see that $S^i_0$ simply consists of the copy of
the source node of token $i$ at level $0$. $T^i$ is constructed on the
nodes in $\cup_{j = 0}^{j = 2l} S^i_j$. If for a vertex $v$,
$v_{2(j+1)} \in S^i_{2(j+1)}$ and $v_{2j} \in S^i_{2j}$, we add the
buffer edge $(v_{2j},v_{2(j+1)})$ in $T^i$. Otherwise, if $v_{2(j+1)}
\in S^i_{2(j+1)}$ but $v_{2j} \notin S^i_{2j}$, we add the selection
edge $(u_{2j},u_{2j+1})$ and broadcast edge $(u_{2j+1},v_{2(j+1)})$ in
$T^i$, where $u$ was the node chosen as described above. It is
straightforward to see that these edges form a directed Steiner tree
for token $i$ as required by the lemma which can be packed in the
evolution graph. The argument is completed by noting that any unit
capacity edge cannot be included in two different Steiner trees as we
started with a broadcast schedule where each node broadcasts a single
token to all its neighbors in one round, and thus all the $k$ Steiner
trees can be simultaneously packed in the evolution graph respecting
the edge capacities.

Next assume that $k$ Steiner trees as in the lemma can be packed in
the evolution graph respecting the edge capacities. We construct a
broadcast schedule for each token from its Steiner tree in the natural
way: whenever the Steiner tree $T_i$ corresponding to token $i$ uses a
broadcast edge $(u_{2j-1},v_{2j})$ for some $j$, we let the node $u$
broadcast token $i$ in round $j$. We need to show that this is a
feasible broadcast schedule. First we observe that two different
Steiner trees cannot use two broadcast edges starting from the same
node because every selection edge has unit capacity, thus there are no
conflicts in the schedule and each node is asked to broadcast at most
one token in each round. Next we claim by induction that if node
$v_{2j}$ is in $T^i$, then node $v$ has token $i$ by the end of round
$j$. For $j = 0$, it is trivial since only the copy of the source node
for token $i$ can be included in $T^i$ from level $0$. For $j > 0$, if
$v_{2j}$ is in $T^i$, we must reach there by following the buffer edge
$(v_{2(j-1)},v_{2j})$ or a broadcast edge $(u_{2j-1},v_{2j})$. In the
former case, by induction node $v$ has token $i$ after round $j-1$
itself. In the latter case, node $u$ which had token $i$ after round
$j-1$ by induction was the neighbor of node $v$ in $G_j$ and $u$
broadcast token $i$ in round $j$, thus implying node $v$ has token $i$
after round $j$. From the above claim, we conclude that whenever a
node is asked to broadcast a token in round $j$, it has the token by
the end of round $j-1$. Thus the schedule we constructed is a feasible
broadcast schedule. Since the copies of all the destination nodes of a
token at level $2l$ are the terminals of its Steiner tree, we conclude
all the tokens reach all of their destination nodes after round $l$.
\end{proof}

\begin{figure}[ht]
\begin{center}
\includegraphics[width=5in]{steiner.jpg}
\caption{An example of building directed Steiner tree in the evolution
  graph $G$ based on token dissemination process. Token $t$ starts
  from node $B$. Thus, the Steiner tree is rooted at $B_0$ in
  $G$. Since $B_0$ has token $t$, we include the infinite capacity
  buffer edge $(B_0,B_2)$. In the first round, node $B$ broadcasts
  token $t$, and hence we include the selection edge
  $(B_0,B_1)$. Nodes $A$ and $C$ receive token $t$ from $B$ in the
  first round, so we include edges $(B_1,A_2)$, $(B_1,C_2)$. Now
  $A_2$, $B_2$, and $C_2$ all have token $t$. Therefore we include the
  edges $(A_2,A_4)$, $(B_2,B_4)$, and $(C_2,C_4)$. In the second
  round, all of $A$, $B$, and $C$ broadcast token $t$, we include
  edges $(A_2,A_3)$, $(B_2,B_3)$, $(C_2,C_3)$. Nodes $D$ and $E$
  receive token $t$ from $C$. So we include edges $(C_3,D_4)$ and
  $(C_3,E_4)$. Notice that nodes $A$ and $B$ also receive token $t$
  from $C$, but they already have token $t$. Thus, we don't include
  edges $(C_3,B_4)$ or $(C_3,A_4)$.}
\label{fig:steiner}
\end{center}
\end{figure}

\input{flow_based_full}
\input{approx_full}
